//tree
class Node{
    constructor(element){
        this.element = element
        this.right = null
        this.left = null
    }
}
class Tree{
    constructor(){
        this.root = null
    }
    //insert
    insert(element){
        let node = new Node(element)
        if(this.root===null){
            this.root = node
        }else{
            this.insertNode(node,this.root)
        }
    }
    insertNode(newNode,rootNode){
        if(newNode.element<rootNode.element){
            if(rootNode.left===null){
                rootNode.left = newNode
            }else{
                this.insertNode(newNode,rootNode.left)
            }
        }else{
            if(rootNode.right===null){
                rootNode.right = newNode
            }else{
                this.insertNode(newNode,rootNode.right)
            }
        }
    }
    min(){
        return this.minNode(this.root)
    }
    minNode(rootNode){
        if(rootNode===null){
            return null
        }
        while(rootNode.left!=null){
            rootNode = rootNode.left
        }
        return rootNode
    }
    max(){
        return this.maxNode(this.root)
    }
    maxNode(rootNode){
        if(rootNode===null){
            return null
        }
        while(rootNode.right!=null){
            rootNode = rootNode.right
        }
        return rootNode
    }
    search(key){
        return this.searchNode(key,this.root)
    }
    searchNode(key,rootNode){
        if(rootNode===null){
            return false
        }
        if(rootNode.element>key){
            return this.searchNode(key,rootNode.left)
        }else if(rootNode.element<key){
            return this.searchNode(key,rootNode.right)
        }else{
            return true
        }
    }
    remove(key){
        this.root = this.removeNode(this.root,key)
        return this.root
    }
    removeNode(rootNode,key){
        if(rootNode===null){
            return false
        }
        if(rootNode.element>key){
            rootNode.left = this.removeNode(rootNode.left,key)
            return rootNode
        }else if(rootNode.element<key){
            rootNode.right = this.removeNode(rootNode.right,key)
            return rootNode
        }else{
            if(rootNode.left===null&&rootNode.right===null){
                rootNode = null
                return rootNode
            }
            if(rootNode.left===null){
                rootNode = rootNode.right
                return rootNode
            }else if(rootNode.right===null){
                rootNode = rootNode.left
                return rootNode
            }
            const endNode = this.minNode(rootNode.right)
            rootNode.element = endNode.element
            rootNode.right = this.removeNode(rootNode.right,endNode.element)
            return rootNode
        }
    }
    pre(){
        this.preNode(this.root)
    }
    preNode(rootNode){
        if(rootNode!==null){
            console.log(rootNode.element);
            this.preNode(rootNode.left)
            this.preNode(rootNode.right)
        }
    }
}
let t = new Tree()
t.insert(15)
t.insert(9)
t.insert(20)
t.insert(7)
t.insert(16)
t.insert(30)
t.insert(11)
console.log(t.min().element,"最小值");
console.log(t.max().element,"最大值");
console.log(t.search(9));
t.remove(15)
t.pre()



